package com.frx.sort;

import java.util.Arrays;

/**
 * @description 归并排序
 * Created by xurenfeng on 2019/2/19.
 */
public class MergeSort{

    public static void main(String[] args){
        int[] arr = {2,7,3,9,8,4,1};
        mergeSort(arr,0,arr.length -1);
        System.out.println(Arrays.toString(arr));
    }

    public static void mergeSort(int[] array,int start,int end){
        if (start < end){
            // 折半成两个小集合，分别进行递归
            int mid = (start + end) / 2;
            mergeSort(array,start,mid);
            mergeSort(array,mid+1,end);
            // 将两个有序小集合归并为一个大集合
            merge(array,start,mid,end);
        }

    }

    private static void merge(int[] array,int start,int mid,int end){
        // 开辟额外大集合
        int[] tempArray = new int[end-start + 1];
        int p1 = start, p2 = mid + 1, p = 0;
        //比较两个小集合的元素，依次放入大集合
        while (p1<=mid && p2 <= end){
            if (array[p1] < array[p2]){
                tempArray[p++] = array[p1++];
            } else {
                tempArray[p++] = array[p2++];
            }
        }
        // 左侧有剩余，复制到大集合中
        while (p1 <= mid){
            tempArray[p++] = array[p1++];
        }
        // 右侧有剩余，复制到大集合中
        while (p2 <= end){
            tempArray[p++] = array[p2++];
        }
        // 大集合的元素复制回原数组
        for (int i=0; i< tempArray.length;i++){
            array[i+start] = tempArray[i];
        }

    }
}
